package com.zzg.datastructure.tree.binarytree;

import com.zzg.datastructure.constant.GlobalConst;
import com.zzg.datastructure.tree.entity.HeroNode;
import lombok.Data;

import java.util.Objects;

/**
 * @Author zhengzg
 * @Date 2022-09-26
 * @Version v1.0
 */
@Data
public class ThreadedBinaryTree {

    private HeroNode root;

    /**
     * 为了实现线索化化，需要创建要给指向当前节点的前驱节点的指针
     */
    private HeroNode pre = null;

    public void threadedNodes() {
        this.threadedNodes(root);
    }

    // 遍历线索化二叉树的方法
    public void threadedList(HeroNode root) {
        // 定义一个变量，存储当前遍历的节点，从root开始
        HeroNode node = root;
        while (Objects.nonNull(node)) {
            // 循环找到leftType == 1的节点，第一个找到就是8节点
            // 后面随着遍历而变化，因为当leftType == 1时，说明该节点是按照线索化
            // 处理后的有效节点
            while (node.getLeftType() == 0) {
                node = node.getLeft();
            }

            // 打印当前这个节点
            System.out.println(node);

            // 如果当前接待你的右指针指向的是后继节点，就一直输出
            while (node.getRightType() == 1) {
                // 获取到当前接待你的后继节点
                node = node.getRight();
                System.out.println(node);
            }
            // 替换这个遍历的节点
            node = node.getRight();
        }
    }

    /**
     * 对二叉树进行中序线索化的方法
     * @param node 当前需要线索化的结点
     */
    public void threadedNodes(HeroNode node) {
        // 如果node == null，不能线索化
        if (Objects.isNull(node)) {
            return;
        }

        // 先线索化左子树
        threadedNodes(node.getLeft());

        // 线索化当前节点
        // 处理当前节点的前驱节点
        if (Objects.isNull(node.getLeft())) {
            // 让当前节点的左指针指向前驱节点
            node.setLeft(pre);
            // 修改当前节点的左指针的类型，指向前驱节点
            node.setLeftType(GlobalConst.YES);
        }

        // 处理后继节点
        if (Objects.nonNull(pre) && Objects.isNull(pre.getRight())) {
            // 让前驱节点的右指针指向当前结点
            pre.setRight(node);
            // 修改前驱节点的右指针类型
            pre.setRightType(GlobalConst.YES);
        }

        // 每处理一个节点后，让当前节点是下一个节点的前驱节点
        pre = node;

        // 在线索化右子树
        threadedNodes(node.getRight());
    }

    // 删除节点
    public void delNode(int no) {
        if (Objects.nonNull(root)) {
            // 如果只有一个root节点，这里判断root是不是要删除的结点
            if (root.getNo() == no) {
                root = null;
            } else {
                // 递归删除
                root.delNode(no);
            }
        } else {
            System.out.println("空树，不能删除~~~");
        }
    }

    // 前序遍历
    public void preOrder() {
        if (Objects.nonNull(this.root)) {
            this.root.perOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    // 中序遍历
    public void infixOrder() {
        if (Objects.nonNull(this.root)) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    // 后序遍历
    public void postOrder() {
        if (Objects.nonNull(this.root)) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    // 前序遍历查找
    public HeroNode preOrderSearch(int no) {
        if (Objects.nonNull(root)) {
            return root.perOrderSearch(no);
        } else {
            return null;
        }
    }

    // 中序遍历查找
    public HeroNode infixOrderSearch(int no) {
        if (Objects.nonNull(root)) {
            return root.infixOrderSearch(no);
        } else {
            return null;
        }
    }

    // 后序遍历查找
    public HeroNode postOrderSearch(int no) {
        if (Objects.nonNull(root)) {
            return root.postOrderSearch(no);
        } else {
            return null;
        }
    }
}
